package tree

//给定一个二叉树，判断其是否是一个有效的二叉搜索树（若它的的左子树不为空，则左子树上所有节点的值均 小于 它的根节点的值;若它的右子树不为空，则右子树上的所有值均 大于 它的根节点的值）
//解决方式：1.中序遍历：检查结果列表是否已经有序
//        2.分治法：判断左Max<root<右min

func IsValidBST(root *Node) bool {
	result := make([]int, 0)
	inOrder(root, &result)
	//check order
	for i := 0; i < len(result)-1; i++ {
		if result[i] >= result[i+1] {
			return false
		}
	}
	return true
}

func inOrder(root *Node, result *[]int) {
	if root == nil {
		return
	}

	inOrder(root.Left, result)
	*result = append(*result, root.Val)
	inOrder(root.Right, result)
}

type ValidBSTResultType struct {
	IsValid bool
	//记录左右两边的最大最小值，和根节点进行比较
	Max *Node
	Min *Node
}

func IsValidBSTWithDivide(root *Node) bool {
	result := isValidBSTHelper(root)
	return result.IsValid
}
func isValidBSTHelper(root *Node) ValidBSTResultType {
	result := ValidBSTResultType{}

	//check
	if root == nil {
		result.IsValid = true
		return result
	}

	left := isValidBSTHelper(root.Left)
	right := isValidBSTHelper(root.Right)

	//Conquer
	if !left.IsValid || !right.IsValid {
		result.IsValid = false
		return result
	}

	if left.Max != nil && left.Max.Val >= root.Val {
		result.IsValid = false
		return result
	}

	if right.Min != nil && right.Min.Val <= root.Val {
		result.IsValid = false
		return result
	}

	result.IsValid = true

	//如果左边还有更小的，右边还有更大的，则重新赋值
	result.Min = root
	if left.Min != nil {
		result.Min = left.Min
	}
	result.Max = root
	if right.Max != nil {
		result.Max = right.Max
	}
	return result
}
